package algorithm.leetcode.I1to100;

import algorithm.leetcode.TreeNode;

/**
 * 验证一颗树是否为BST
 * BST定义:
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 时刻牢记BST的中序遍历是 **严格** 递增序列
 */

public class Q98 {

    TreeNode prev;
    boolean result = true;

    public boolean isValidBST(TreeNode root) {
        inorder(root);
        return result;
    }

    public void inorder(TreeNode node) {
        if (node == null) return;

        inorder(node.left);
        if (prev != null) result &= prev.val < node.val;
        prev = node;
        inorder(node.right);
    }

    public static void main(String[] args) {
        Q98 q98 = new Q98();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(6);
        // TreeNode node6 = new TreeNode(6);
        node1.left = node2;
        // node1.right = node3;
        // node3.left = node4;
        // node3.right = node5;
        // node5.right = node6;
        System.out.println(q98.isValidBST(node1));
    }
}
